Hilbert's tenth problem について

Words near each other

Dictionary Lists

mini英和辞書

mini和英辞書

翻訳と辞書　辞書検索 [ 開発暫定版 ]

スポンサードリンク

Hilbert's tenth problem ：ウィキペディア英語版

Hilbert's tenth problem
Hilbert's tenth problem is the tenth on the list of Hilbert's problems of 1900. Its statement is as follows:

Given a Diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: ''To devise a process according to which it can be determined in a finite number of operations whether the equation is solvable in rational integers''.

It took many years for the problem to be solved with a negative answer. Today, it is known that no such algorithm exists in the general case because of the Matiyasevich/MDRP theorem that states that recursively enumerable sets are equivalent to diophantine sets. This result is the combined work of Martin Davis, Yuri Matiyasevich, Hilary Putnam and Julia Robinson〔S. Barry Cooper, ''Computability theory'', p. 98〕 which spans 21 years, with Yuri Matiyasevich completing the theorem in 1970.
==Formulation==

The words "process" and "finite number of operations" have been taken to mean that Hilbert was asking for an algorithm. The term "rational integer" simply refers to the integers, positive, negative or zero: 0, ±1, ±2, ... . So Hilbert was asking for a general algorithm to decide whether a given polynomial Diophantine equation with integer coefficients has a solution in integers. Such an equation can be put in the form
:

p(x_1,x_2,\ldots,x_n)=0 .

where ''p'' is a polynomial with integer coefficients.
The answer to the problem is now known to be in the negative: no such general algorithm can exist. Although it is unlikely that Hilbert had conceived of such a possibility, before going on to list the problems, he did presciently remark:

"Occasionally it happens that we seek the solution under insufficient hypotheses
or in an incorrect sense, and for this reason do not succeed. The problem then arises: to show the impossibility of the solution under the given hypotheses or in the sense contemplated."

The work on the problem has been in terms of solutions in natural numbers〔Following the tradition in mathematical logic,

0

is considered to be a natural number in this article.〕 rather than arbitrary integers. But it is easy to see that an algorithm in either case could be used to obtain one for the other. If one possessed an algorithm to determine solvability in natural numbers, it could be used to determine whether an equation in

n

unknowns,
:

p(x_1,x_2,\ldots,x_n)=0,\,

has an integer solution by applying the supposed algorithm to the 2^''n'' equations
:

p(\pm x_1, \pm x_2,\ldots,\pm x_n)=0. \,

Conversely, an algorithm to test for solvability in arbitrary integers could be used to test a given equation for solvability in natural numbers by applying that supposed algorithm to the equation obtained from the given equation by replacing each unknown by the sum of the squares of four new unknowns. This works because of Lagrange's four-square theorem, to the effect that every natural number can be written as the sum of four squares.

抄文引用元・出典: フリー百科事典『ウィキペディア（Wikipedia）』
■ウィキペディアで「Hilbert's tenth problem」の詳細全文を読む

スポンサードリンク

翻訳と辞書 : 翻訳のためのインターネットリソース